/**
 *
 * David Witwer
 * Walter Lehner
 * Professor Rager
 * CS 241
 */

import java.util.Vector;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import java.util.Vector;

public class SearchBase {

        private static final int PRINT_HOW_OFTEN = 10000;
        public static boolean debug = false;
    //For IDA search
       public static int increment = 1;


        public static void main(String[] args)  {
	    //User must choose depth limit and search type. First number is the search type, and for those relevant, the second is the limit
	    //Breadth First(1),bounded depth first(2), DFID(3), A*(4), or IDA*(5)
	    //Note that the IDA* search uses f(n) values for its limits. Thus place limits in an appropriate range
	    //I have included an int to control the incrementation of the IDA* search

	    //Other systems that I might want to try...
	    //System.out.println("Choose your preferred search method: Breadth first search(1), Bounded Depth First Search(2), Depth First search with interative deepening(3), A*, or A* with Interative deepening(5)");
            //String str = JOptionpane.showInputDialog(null,"Enter String");
	    //int searchType= Integer.parseInt(System.in.readln());
      int depth_limit;
	    
	    int searchType = Integer.parseInt(args[0]);
          if((searchType==2)||(searchType==3)||(searchType||5)){
              depth_limit = Integer.parseInt(args[1]); 
            if(searchType!=5){  
              System.out.println("Depth Limit: "+depth_limit);
            }
            else 
              System.out.println("F Limit: " + depth_limit);
          }
          else
            depth_limit = 1;

                new SearchBase().process(depth_limit, searchType);
        }

    private void process(int depth_limit, int searchType) {

	    //String start = "123/784/65x";
                String start = "216/4x8/753";
                String goal = "123/8x4/765";

                PassBoolean p = new PassBoolean();
		//I left the searchtype in the passboolean because it is everywhere and easy to access.
		//this is not particularly intuitive, but it was convinient 
		p.setSearch(searchType);

                int NEXT_DEPTH = depth_limit + 1;
		//Does DFID and IDA* (note, to do IDA* it currently needs to be told in state.java
		if(searchType==3){
		     DFIDSearch(p , depth_limit, new EightPuzzle(start, goal), p);
		}	
		if(searchType==5){
		     IDASearch(p , depth_limit, new EightPuzzle(start, goal), p);
		}


		//Note: A* and BFS
    if(searchType==4){
		    NEXT_DEPTH = ASearch(p , depth_limit, new EightPuzzle(start, goal));
		}
    
		if(searchType==1){
		    NEXT_DEPTH = bestFirstSearch(p , depth_limit, new EightPuzzle(start, goal));
		}

		    //Note: bounded depth first
	       if(searchType==2){
		   NEXT_DEPTH = vectorSearch(p, depth_limit, new EightPuzzle(start, goal));  
	       }
                
                System.out.println("The goal was found: "+p.getValue());
		if(p.getValue()==false){
		    System.out.println("Suggested next depth is "+NEXT_DEPTH);
		}


        }

        public int search(PassBoolean done, int limit, StateSpace ssp, SearchList open) {

                System.out.println("Starting search with limit "+ limit);

                open.add(new State(ssp.getStart(),ssp.getGoal(), done.getSearch()));

                int count = 0;

                while (!done.getValue()) {

                        if (open.size()==0) {
                                System.out.println("open list empty at "+count);
                                break;
                        }

                        State current =  open.remove();
                        count++;
                        if (count % PRINT_HOW_OFTEN == 0) {
                                System.out.println("Search limit "+limit+" at Node # "+
                                                count+" Open list length:"+open.size()+" Current Node "+
                                                current.getRep()+"  Depth: "+current.getDepth());
                        }
                        if (ssp.isGoal(current.getRep())) {
                                done.set(true);
                                System.out.println(count+"> found goal at "+current.getRep()+" at depth"+current.getDepth());
                                current.printPath();
                                break;
                        }

                        if (current.getF() < limit) {
                                Vector<String> kids = ssp.getKids(current.getRep());

                                for (String v : kids) {
                                        if (!current.getPath().contains(v))
                                                open.add(new State(current,v));
                                }
                        }
                }
                return limit+1;
        }


        public int vectorSearch(PassBoolean done, int limit, StateSpace ssp) {
	    //	    System.out.println("Depth First search");

                return search(done,limit,ssp,new VectorasList());
        }

    //breadthfirst (not best first)
        public int bestFirstSearch(PassBoolean done, int limit, StateSpace ssp) {

                return search(done,limit,ssp,new SearchQueue());
        }
        //A*
        public int ASearch(PassBoolean done, int limit, StateSpace ssp) {

                return search(done,limit,ssp,new PQasList());
        }
    //DFID
        public void DFIDSearch(PassBoolean done, int limit, StateSpace ssp, PassBoolean p) {
	    //	    System.out.println("Depth first interative deepening search");
                int l=search(done,limit,ssp,new VectorasList());
                while(!p.getValue()){
                   l=  search(done,l,ssp,new VectorasList());
                }
        }
    //IDA*
    public void IDASearch(PassBoolean done, int limit, StateSpace ssp, PassBoolean p) {
	    //	    System.out.println("Interative Deepening A*");
                int l=search(done,limit,ssp,new VectorasList());
                while(!p.getValue()){
                    search(done,l,ssp,new VectorasList());
		    l+= increment;
                }
        }
}


